package next_flag_search;

import env.Action;
import env.Enviroment;
import env.Tile;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Vector;

/**
 *
 * @author user
 */
public class AStar extends Search {
    private Vector<Tile> flags = null;

    private int abs(int x) {
        return x >= 0 ? x : -x;
    }
    //h(n) = manhattan distance from nearest flag.
    private int h(Node n) {
        int d = Integer.MAX_VALUE;
        for (Tile flag : flags) {
            int temp = abs(n.getRow() - flag.getRow()) + abs(n.getCol() - flag.getCol());
            if (temp < d) {
                d = temp;
            }
        }
        return d;
    }
    
    //h(n) = manhattan distance from ALL flags.
    private int h2(Node n) {
        int d = 0;
        for (Tile flag : flags) {
            d+= abs(n.getRow() - flag.getRow()) + abs(n.getCol() - flag.getCol());
        }
        return d;
    }
    

    private void findAllFlags() {
        Enviroment env = Enviroment.env;
        flags = new Vector<Tile>();
        for (int i = 0; i < env.rows; i++) {
            for (int j = 0; j < env.cols; j++) {
                if (env.map[i][j].hasFlag()) {
                    flags.add(env.map[i][j]);
                }
            }
        }
    }

    @Override
    public LinkedList<Action> search() {
        
        findAllFlags();
        MyQueue q=new MyQueue(){
            PriorityQueue<Node> queue=new PriorityQueue<Node>(10, new Comparator<Node>(){
            /**
             * return positive if first is greater then second.
             */
            @Override
            public int compare(Node o1, Node o2) {
                return h(o1)+o1.getG()-h(o2)-o2.getG();
            }
        });
            public Node poll() {
                return queue.poll();
            }

            public void add(Node n) {
                queue.add(n); 
            }

            public boolean isEmpty() {
                return queue.isEmpty();
            }
            
        };
        
        return super.graphSearch(q);
        
    }    
}
